package week02

import "sort"

// 1122. 数组的相对排序
// https://leetcode-cn.com/problems/relative-sort-array/

func relativeSortArray(arr1 []int, arr2 []int) []int {
	var maxVal = 0
	for _, v := range arr1 {
		maxVal = max(maxVal, v)
	}
	var count = make([]int, maxVal+1)
	for _, v := range arr1 {
		count[v]++
	}
	var ans = make([]int, 0, len(arr1))
	for _, v := range arr2 {
		for count[v] > 0 {
			ans = append(ans, v)
			count[v]--
		}
	}
	sort.Sort(sort.IntSlice(arr1))
	for _, v := range arr1 {
		if count[v] > 0 {
			ans = append(ans, v)
		}
	}
	return ans
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}